package com.enjoy.leetcode;

/**
 * 5. 最长回文子串
 * 中心扩散法
 */
public class ch5 {

    static class Solution {

        public String longestPalindrome(String s) {
            if (s == null || "".equals(s)) {
                return null;
            }

            int start = 0;
            int end = 0;

            for (int i = 0; i < s.length(); i++) {

                int len1 = expand(s, i, i);
                int len2 = expand(s, i, i + 1);
                int len = Math.max(len1, len2);

                if (len > end - start) {
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }

            }
            return s.substring(start, end + 1);
        }

        private int expand(String s, int left, int right) {
            int l = left;
            int r = right;
            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                l--;
                r++;
            }
            return r - l - 1;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println("solution.longestPalindrome(\"babad\") = " + solution.longestPalindrome("babad"));
    }
}
